\chapter{Wprowadzenie}

Coraz częściej w wielu dziedzinach nauki próbuje się opisywać otaczający nas
świat za pomocą systemów złożonych z wielu jednostek, które wzajemnie na siebie
oddziałują i konkurują ze sobą.
Takie podejście jest szeroko wykorzystywane na przykład w socjologii, biologii
i medycynie, ekonomii oraz finansach.

Najprostsze tego typu modele, w myśl darwinowskiej koncepcji ewolucji i doboru
naturalnego \cite{opg}, zakładają, że przewagę zawsze zyskują osobniki lepiej
przystosowane do środowiska (ang. \emph{Survival of the fittest}).
W innych dopuszcza się dalej idące uproszczenia i przyjmuje się, że najlepszą
strategią ewolucyjną jest racjonalne, ale i egoistyczne, maksymalizowanie
własnych korzyści.
Okazuje się jednak, że przyrodą rządzą bardziej skomplikowane i subtelne
mechanizmy.
Na przykład nietoperze z gatunku \emph{Desmodus rotundus}, którym nie uda się
polowanie, mogą liczyć, że ich stado podzieli się z nimi posiłkiem.
Zwiększa to szanse na przeżycie całej populacji.
Surykatki \emph{Suricata suricatta} w obronie swojego stada wydają dźwięki
mające na celu ostrzeżenie reszty osobników, pomimo że tym samym zwracają uwagę
drapieżnika na siebie.
Szczury zawsze przed posiłkiem sprawdzają czy jedzenie nie jest trujące.
W tym celu delegowany jest przedstawiciel, który próbuje pokarmu.
Na podstawie jego reakcji reszta stada wnioskuje czy może przystąpić do uczty.

To tylko niektóre z wielu przykładów \cite{ewa}.
Pokazują one, że natura potrafi stworzyć dogodne warunki do rozwoju
\emph{współpracy}.
Wpływa ona na zwiększenie przystosowania całej populacji kosztem, być może,
korzyści niektórych jednostek.
Modele wspomniane wyżej nie dopuszczają jednak do pojawiania się zachowań
altruistycznych.
Widać zatem potrzebę konstruowania systemów lepiej odzwierciedlających
rzeczywistość.
To jeden z najlepszych sposobów na zgłębienie fenomenalnego
zjawiska, jakim jest pojawianie się w przyrodzie \emph{kooperacji}.

\section{Teoria Gier}

Matematykowi niezbędnych narzędzi do analizy postawionego wyżej problemu
dostarcza \emph{Teoria Gier}.
Jest to jedna z najmłodszych dziedzin matematyki.
Teoria gier zajmuje się opisem i analizą sytuacji, w których pewna liczba
jednostek wchodzi ze sobą we wzajemną interakcję.
W zależności od przyjętego zachowania, jednostki mogą spotkać różne
konsekwencje.
Takie sytuacje nazywamy \emph{grami}, jednostki \emph{graczami}, a możliwe
zachowania graczy \emph{strategiami}.
Rezultat gry może mieć różną wartość dla poszczególnych graczy.
Wartość tę nazywamy\emph{wypłatą} i definiujemy osobno dla każdego gracza.

Często staramy się odpowiedzieć na pytanie, jakie strategie powinni stosować
racjonalnie myślący i inteligentni (czyli dążący do zmaksymalizowania swojej
wypłaty) gracze.
W tym celu wprowadzono pojęcie \emph{Równowagi Nasha}.
Mówimy, że równowaga ta ma miejsce, gdy gracze wybiorą takie strategie, że
zmiana decyzji dowolnego z nich nie spowoduje zwiększenia jego wypłaty.
W takiej sytuacji racjonalne zachowanie każdego gracza polega na trwaniu
przy swoim wyborze.

\section{Dylemat Więźnia}\label{wstepDoDylematu}

Przyjrzyjmy się podanym niżej przykładom kilku problemów decyzyjnych.

Na początek rozważmy często występującą w zawodach kolarskich sytuację, w której
dwóch zawodników ucieka przed peletonem.
Zazwyczaj zmieniają się oni na męczącej, pierwszej pozycji.
Jeśli żaden zawodnik nie będzie się starał jechać jako pierwszy, wówczas
najprawdopodobniej peleton szybko ich dogoni.
Z drugiej strony, jeśli tylko jeden z nich będzie to robił, to istnieje duża
szansa, że zawodnik, który jechał za nim (i dzięki temu mniej się męczył)
wyprzedzi go tuż przed metą.

Inny przykład problemu to dwa państwa uwikłane w wyścig zbrojeń.
Każde z nich ma dwie możliwości, albo zwiększać nakłady na zbrojenia, albo
podpisać porozumienie o ich zawieszeniu.
Korzystniejszym rozwiązaniem byłoby ograniczenie wydatków związanych z
przemysłem militarnym.
Żadna ze stron nie może być jednak pewna czy przeciwnik dotrzyma słowa.
W rezultacie najlepsze wyjście to kontynuowanie rozwoju militarnego.

Kolejny scenariusz odnosi się do towarów, które ludzie kupują niezależnie od
tego czy są reklamowane czy nie.
Na przykład papierosy --- jeśli kilka koncernów tytoniowych sprzedaje swoje
produkty na tym samym runku, to zysk każdego z nich zależy głównie od tego ile
sprzedadzą konkurenci.
W przypadku gdy wszystkie firmy przeznaczają duże kwoty na reklamę swoich
produktów, to efekty kampanii się znoszą.
Jednak jeśli tylko jedna firma się reklamuje, to zdobywa dużą przewagę nad
resztą.
Wobec tego każdej firmie powinno zależeć na tym, aby wszyscy ograniczyli wydatki
na reklamę.
Nic dziwnego więc, że w USA koncerny tytoniowe bardzo aktywnie wspierały
uchwalenie prawa zabraniającego reklamowanie papierosów.

Klasyczny przykład opisuje sytuację dwóch podejrzanych, którzy zostali
złapani przez policję, ale nie ma dostatecznych dowodów do postawienia im
zarzutów.
Dlatego funkcjonariusze rozdzielają więźniów i każdemu z nich przedstawiają tę
samą ofertę.
Jeśli jeden będzie zeznawać przeciwko drugiemu, a drugi będzie milczeć, to
zeznający wyjdzie na wolność, a milczący dostanie dziesięcioletni wyrok.
Jeśli obaj będą milczeć, to każdy dostanie sześć miesięcy odsiadki za inne
przewinienia.
Jeśli z kolei obaj będą zeznawać, to dostaną pięcioletnie wyroki.
Więźniowie muszą podjąć decyzję niezależnie, nie wiedząc jak postąpił
współuczestnik niedoli aż do momentu ogłoszenia wyroku.
Jak powinni postąpić?

\medskip

Pozornie nie mają ze sobą nic wspólnego, ale w rzeczywistości są to szczególne
przypadki tego samego problemu.
Wszystkie powyższe sytuacje można opisać przy pomocy bardzo prostej
\emph{symetrycznej gry dwuosobowej}
(patrz \ref{graSymDwuosobowa}) nazywanej
\emph{Dylematem Więźnia} (ang. \emph{Prisoner's Dilemma}).
W teorii gier jest to często rozważany model sytuacji kryzysowej, w której
jesteśmy zmuszeni wybierać między własnym interesem, a dobrem ogółu.
Każdy z graczy ma do wyboru dwie strategie: \emph{współpracę} $C$ i
\emph{zdradę} $D$.
Współpraca symbolizuje przedkładanie wspólnego dobra nad własne interesy.
Zdrada to strategia maksymalizowania własnych korzyści kosztem drugiego gracza.
W tej grze najwyższą wypłatę zawsze dostaje zdrajca, który wykorzystuje
naiwnie kooperującego rywala.
Natomiast najwyższą średnią wypłatę otrzymują dwaj gracze, którzy współpracują.
Przykładowe wartości wypłat przedstawiają się następująco:
(por. \ref{macierzWyplat}):
\[
\begin{array}{c|cc}
 & C & D\\
\hline
C & 3 & 0\\
D & 5 & 1\\
\end{array}
\]

Zauważmy, że jedyną równowagą Nasha
(zob. \ref{rownowagaNasha}) w tej grze jest sytuacja,
w której gracze nawzajem się zdradzają.
Z drugiej strony o wiele korzystniejszy byłby dla nich wybór kooperacji.
Ta sytuacja ma swoje podłoże w głębokim tragizmie gry.
Jak z tym problemem radzi sobie zatem natura?

Próba odpowiedzenia na to pytanie skłoniła nas do rozpoczęcia poszukiwań
modelu, który zdołałby odzwierciedlić subtelną złożoność badanego przez
nas świata, a jednocześnie na tyle prostego, żeby możliwa była analiza jego
właściwości.

\section{Znane rezultaty}

Jedno z pierwszych podejść do tego tematu zostało zaproponowane w 1984 roku w
książce Roberta Axelrod'a zatytułowanej \emph{The Evolution of Cooperation}
\cite{teoc}.
Zastąpił on pojedynczą grę całą ich serią, a graczom pozwolił podejmować decyzje
na podstawie historii zagrań danego przeciwnika.
W takim modelu gracz wybierający zdradę musi liczyć się z tym, że w
przyszłości może zostać ukarany za swoje posunięcie.
Axelrod zorganizował turniej komputerowych programów implementujących
różne strategie gry w \emph{iterowany} dylemat więźnia.
Okazało się, że najlepsze wyniki osiągnęła najprostsza zgłoszona propozycja
 --- \emph{wet za wet} (ang. \emph{tit for tat}).
Według niej na początku należy zagrać $C$, a potem to co przeciwnik w poprzednim
kroku.
Zaintrygowany wynikami turnieju, Axelrod przeprowadził dokładną analizę modelu i
udowodnił, że strategia \emph{tit for tat} jest rzeczywiście najlepsza.

Innym podejściem jest Ewolucyjna Teoria Gier.
W tym przypadku wypłaty graczy traktuje się jako miarę ich przystosowania do
środowiska i szansę wydania potomstwa.
Najprostszy model populacji, w której interakcje zachodzą między losowo
spotkanymi graczami (ang. \emph{well--mixed populations}), znów niestety
% DL: miedzy slowami stosuje sie - a nie --
prowadzi zdradzających graczy do ewolucyjnego zwycięstwa \cite{gte}.
Okazuje się jednak, że umieszczenie populacji w przestrzeni i zamodelowanie
lokalności oddziaływań między graczami wystarczy już, aby pojawiła się
kooperacja.
Po raz pierwszy takie podejście zaproponowali Nowak i May \cite{nm} w 1992 roku.
Rozważali oni dylemat więźnia rozgrywany na kwadratowej siatce przez graczy bez
żadnej pamięci.
Przeprowadzone przez nich symulacje komputerowe pokazały, że w takich warunkach
kooperacja może przetrwać.
Ich wyniki zostały potwierdzone między innymi przez Feldmana \cite{krfb} i
Hauerta \cite{hd}.

W ciągu następnych lat model ten stał się bardzo popularny i doczekał się
wielu uogólnień.
Jeden z kierunków badań polegał na rozszerzenie koncepcji Nowaka na sieci
nieregularne o różnych topologiach, gdyż podejrzewano, że takie grafy lepiej
odzwierciedlają złożoność rzeczywistych powiązań społecznych.
Niestety nie ustrzeżono się błędów.
Na przykład Bartosz Sułkowski zauważył że niektóre uogólnienia,
polegające na zmianie wszystkich wypłat o pewną ustaloną wartość, mogą zmienić
jakościowy stosunek sum wypłat graczy o różnej liczbie sąsiadów i tym samym
mieć istotny wpływ na zachowanie modelu w czasie \cite{bs}.

Widać zatem, że zagadka istoty kooperacji została do tej pory wyjaśniona tylko
częściowo.

\section{Zakres pracy}

W naszej pracy zajmujemy się kolejnym uogólnieniem koncepcji gier ewolucyjnych.
Rozważamy sieci, które zmieniają się wraz z populacją.

W rozdziale \emph{\nameref{podstawowePojecia}} przypominamy
podstawowe definicje i terminy, którymi posługujemy się w całej pracy.

W kolejnej części, zatytułowanej \emph{\nameref{modelPolski}}, opisujemy system
oparty o model rzeczywistej sieci powiązań społecznych w społeczeństwie Polski.
Badamy jak na zachowanie populacji wpływają, niezależne od wyników
przeprowadzanych gier, zmiany sieci odzwierciedlające podróże członków
społeczeństwa.
Rozważana przez nas sieć społeczna obejmuje ponad $35,\!8$ miliona wierzchołków.
Krawędzie grafu odzwierciedlają relację znajomości, która wyznaczona jest
poprzez przynależność graczy do różnych grup społecznych.
Dynamika populacji to proces Morana.
Nasze badania potwierdzają wyniki uzyskane przez Santosa \cite{sp} ---
średni poziom kooperacji wynosi około $83\%$.
To oznacza, że kooperacja promuje się nie tylko w matematycznych modelach sieci
społecznych, ale także w ich rzeczywistych odpowiednikach.
Odkryliśmy także, że duże grupy społeczne (zrzeszające kilkudziesięciu i więcej
członków) charakteryzują się bardzo wysokim poziomem kooperacji.
Z drugiej strony w grupach kilkuosobowych, które obejmują zazwyczaj najbliższą
rodzinę, współpraca pojawia się znacznie rzadziej.

Dalej w rozdziale \emph{\nameref{uogolnioneGryPrzestrzenne}} wprowadzamy model,
w którym dynamika populacji i sieci wzajemnie na siebie wpływają i przeplatają.
Realizujemy to poprzez odzwierciedlanie sympatii, jaką gracze mogą darzyć się
nawzajem. Całość formalizujemy używając łańcuchów Markowa w części
\ref{dynamikaJakoLancuchMarkowa}, a wyniki symulacji
przedstawione są w punkcie \ref{uogSymulacje}.
Tam też, na przykładzie grafu pełnego, zastanawiamy się nad stabilnością
prezentowanych układów, a także formułujemy najistotniejsze spostrzeżenia.

W \emph{\hyperref[podsumowanie]{Podsumowaniu}} prezentujemy najważniejsze
wyniki i przedstawiamy płynące z nich wnioski.

